# need py 3.8

from typing import List
from more_itertools import pairwise

class Solution:
    def uniquePathsIII(self, 地图: List[List[int]]) -> int:
        
        def 为起点(行, 列):
            return 地图[行][列] == 1
        
        def 为终点(行, 列):
            return 地图[行][列] == 2

        def 为障碍(行, 列):
            return 地图[行][列] == -1
        
        def 深度优先搜索(行: int, 列: int, 已经过格数: int) -> int:
            if 为终点(行, 列):
                return int(已经过格数 == 需经过格数 + 1)
            路径条数 = 0
            for 上下, 左右 in pairwise(各方向):
                行号, 列号 = 行 + 上下, 列 + 左右
                if 0 <= 行号 < 行数 and 0 <= 列号 < 列数 and \
                    (行号, 列号) not in 已经过 and not 为障碍(行号, 列号):
                    已经过.add((行号, 列号))
                    路径条数 += 深度优先搜索(行号, 列号, 已经过格数 + 1)
                    已经过.remove((行号, 列号))
            return 路径条数

        行数, 列数 = len(地图), len(地图[0])
        起点 = next((行, 列) for 行 in range(行数) for 列 in range(列数) if 为起点(行, 列))
        各方向 = (-1, 0, 1, 0, -1)
        需经过格数 = sum(行.count(0) for 行 in 地图)
        已经过 = {起点}
        return 深度优先搜索(*起点, 0)






s = Solution()
print(s.uniquePathsIII([[1,0,0,0],[0,0,0,0],[0,0,2,-1]]))
print(s.uniquePathsIII([[1,0,0,0],[0,0,0,0],[0,0,0,2]]))
print(s.uniquePathsIII([[0,1],[2,0]]))
